/*
 * Package il.ac.biu.cs.grossmm.api.activeData
 * File Cache.java
 * 
 * This is a part of presence service framework prototype. 
 * See javadoc for more information.
 *  
 * Copyright (C) 2006 Grossmann Mark
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.

 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */
package il.ac.biu.cs.grossmm.impl.activeData;

import il.ac.biu.cs.grossmm.api.OperationFailedException;

import java.util.concurrent.ConcurrentHashMap;

/**
 * Generic implementation of a memory cache. From the API point of view the
 * cache is similar to a hash-map, however as a rule only frequently used values
 * are stored in the memory whereas the others are provided by some plugged-in
 * data retreival mechanism (e.g. from retreived from relational data base or
 * computed on fly).
 * 
 * @param <K>
 *            key type
 * @param <V>
 *            value type
 */
public class Cache<K, V> {
	/**
	 * The key value pair
	 * @author mg
	 *
	 * @param <K>
	 * @param <V>
	 */
	static class Entry<K, V> {
		private V value;

		private final K key;

		private Entry<K, V> prev;

		private Entry<K, V> next;

		public Entry(K key, V value) {
			this.value = value;
			this.key = key;
		}

		/**
		 * @return the value
		 */
		public V getValue() {
			return value;
		}

		/**
		 * @param value
		 *            the value to set
		 */
		public void setValue(V value) {
			this.value = value;
		}

		/**
		 * @return the key
		 */
		public K getKey() {
			return key;
		}
	}

	/**
	 * The priority queue of key-value pairs, where the queue head is the
	 * entry which has been most recently used, and the tail is the entry
	 * which was not accessed longer than any other entry in the queue.
	 * <p>
	 * From the implementation point of view this queue is basically a
	 * doubly linked list
	 *
	 * @param <K> key type
	 * @param <V> value type
	 */
	static class Queue<K, V> {
		/**
		 * The queue head
		 */
		Entry<K, V> head;

		/**
		 * The queue tail
		 */
		Entry<K, V> tail;

		/**
		 * The queue CTOR
		 *
		 */
		Queue() {
			// use dummy etries for head and tail
			head = new Entry<K, V>(null, null);
			tail = new Entry<K, V>(null, null);

			// link head and tail 
			head.next = tail;
			tail.prev = head;
		}

		/**
		 * size of the queue
		 */
		private volatile int size;

		public int size() {
			return size;
		}

		/**
		 * Adds a new entry to the queue
		 * @param entry
		 */
		synchronized void enqueue(Entry<K, V> entry) {
			assert entry != null;

			Entry<K, V> next = head.next;

			assert next != null;

			head.next = entry;

			entry.next = next;
			entry.prev = head;

			next.prev = entry;

			size++;

			assert tail.prev.prev != null;
		}

		synchronized void remove(Entry<K, V> entry) {
			assert (entry != null);

			Entry<K, V> prev = entry.prev;

			if (prev == null)
				return;

			Entry<K, V> next = entry.next;

			assert (next != null);

			prev.next = next;
			next.prev = prev;

			// flag the entry as removed
			entry.prev = null;

			size--;

			assert tail.prev != entry;
		}

		synchronized Entry<K, V> dequeue() {
			Entry<K, V> e = tail.prev;

			if (e != head) {
				remove(e);
				return e;
			} else
				return null;
		}

		synchronized void pop(Entry<K, V> entry) {
			assert entry != null;
			assert tail.prev.prev != null;

			Entry<K, V> first = head.next;
			if (entry == first)
				return;

			Entry<K, V> prev = entry.prev;
			if (prev == null)
				return;

			assert first != null;

			Entry<K, V> next = entry.next;

			assert next != null;

			// remove entry from the current position
			prev.next = next;
			next.prev = prev;

			// insert entry between the head and the first element
			first.prev = entry;
			head.next = entry;

			entry.next = first;
			entry.prev = head;

			assert tail.prev.prev != null;
		}
	}

	/**
	 * Map from key to entry (key-value pair)
	 */
	ConcurrentHashMap<K, Entry<K, V>> map;

	/**
	 * The data retriever to use to get data when cahche-miss occurs
	 */
	final DataRetriever<K, V> retriever;

	/**
	 * The priority queue of entries
	 */
	final Queue<K, V> queue;

	/**
	 * Maximal size of the queue (=maximal size of the cache)
	 */
	final int maxSize;

	/**
	 * Create the new cache backed by a given data retreiver
	 * @param retriever the data retreiver for the cache
	 * @param maxSize maximal cache size
	 */
	Cache(DataRetriever<K, V> retriever, int maxSize) {
		this.retriever = retriever;
		this.maxSize = maxSize;
		this.queue = new Queue<K, V>();

		map = new ConcurrentHashMap<K, Entry<K, V>>();
	}

	/**
	 * Get value for the key
	 * @param key the key
	 * @return value associated with this key
	 * @throws OperationFailedException
	 */
	public V get(K key) throws OperationFailedException {
		assert key != null;

		// try to get the key-value entry from the cache
		Entry<K, V> entry = map.get(key);

		if (entry == null) {
			// cache miss, use data retreiver to obtain the key
			// atomically put the new value to the cache if still missing
			entry = setIfAbsent(key, retriever.retrieve(key));
		} else {
			// move the entry to the head of the queue
			queue.pop(entry);
		}

		// return the requested value
		return entry.value;
	}

	/**
	 * Checks whether the value for the given key is cached
	 * @param key the key
	 * @return true iff the value for the given key is cached
	 */
	public boolean isCached(K key) {
		return map.contains(key);
	}

	private Entry<K, V> setIfAbsent(K key, V value) {
		Entry<K, V> entry = new Entry<K, V>(key, value);

		synchronized (this) {
			Entry<K, V> e2 = map.putIfAbsent(key, entry);
			if (e2 == null) {
				queue.enqueue(entry);
				checkMaxSize();
			} else
				entry = e2;
		}

		return entry;
	}

	private synchronized void set(K key, V value, boolean allowNew) {
		Entry<K, V> entry = new Entry<K, V>(key, value);
		Entry<K, V> oldEntry = map.get(key);

		if (allowNew || oldEntry != null) {
			if (oldEntry == null) {
				queue.enqueue(entry);
				checkMaxSize();
			}

			map.put(key, entry);
		}
	}

	/**
	 * Ensures that cache size (=queue size) does not exceed maximum size.
	 * Should be called within synchronzied block on this cache
	 * 
	 */
	private void checkMaxSize() {
		while (queue.size() > maxSize) {
			Entry<K, V> removedEntry = queue.dequeue();
			map.remove(removedEntry.getKey());
		}
	}

	/**
	 * Called when a key-value association changes for some key
	 * @param key the key
	 * @throws OperationFailedException
	 */
	public void update(K key) throws OperationFailedException {
		set(key, retriever.retrieve(key), false);
	}

	
	/**
	 * Called when a key-value association changes for some key
	 * @param key the key 
	 * @param value the new value
	 */
	public void update(K key, V value) {
		set(key, value, false);
	}

	/**
	 * Uncaches the key
	 * @param key the key to remove from the cache
	 */
	public void remove(K key) {
		Entry<K, V> entry = map.remove(key);

		if (entry != null)
			queue.remove(entry); // double remove is ok (no race condition)
	}
}
